package com.base.dynamicprograming;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 264. 丑数 II
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 * <p>
 * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
 *
 * @author leon
 * @date 2021年12月10日 20:11
 */
public class NthUglyNumber {

    //    方法一使用最小堆，会预先存储较多的丑数，导致空间复杂度较高，维护最小堆的过程也导致时间复杂度较高
    public int nthUglyNumber(int n) {
        // 通过集合判断重复元素
        Set<Long> set = new HashSet<>();
        PriorityQueue<Long> heap = new PriorityQueue<>();
        int[] multipliers= new int[]{2,3,5};
        set.add(1L);
        heap.offer(1L);
        int ugly= 0;
        for (int i = 0; i < n; i++) {
            long poll = heap.poll();
            ugly = (int) poll;

            for (int multiplier:multipliers){
                Long tmp =multiplier*poll;
                // 可能出现重复元素，出现重复元素时，就不向堆里加入。
                if(set.add(tmp)){
                    heap.add(tmp);
                }
            }
        }
        return ugly;
    }

    /**
     * 动态规划：
     *
     * @param n
     * @return
     */
    public int nthUglyNumber1(int n){
        // p1,p2,p3 代表的是定义三个指针 p_2,p_3,p_5p
        // ，表示下一个丑数是：   当前指针指向的丑数乘以对应的质因数
        //  可以理解存在三个丑数数组，他们分别是含有2，3，5质因数的，然后将其合并到一个数组中来。
        // dp数组 代表是 丑数数组（从小到大）
        int p1=1,p2=1,p3=1;
        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int u1 = dp[p1]*2;
            int u2 = dp[p2]*3;
            int u3 = dp[p3]*5;
            int ugly = Math.min(u1,Math.min(u2,u3));
            dp[i] = ugly;
            if(ugly == u1){
                p1++;
            }
            if(ugly == u2){
                p2++;
            }
            if(ugly == u3){
                p3++;
            }
        }

        return dp[n];
    }


    public static void main(String[] args) {
    }

}
